package two.chapter_5.c5_1;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_1.c1_1.Printer;
import two.chapter_2.c2_1.InsertionSort;

public class MSD {
    private static int R=256;
    private static int M=15;
    private static String[]aux;
    private static int charAt(String s,int d){
        if (d<s.length())
            return s.charAt(d);
        return -1;
    }

    public static void sort(String[] a){
        int N=a.length;
        aux=new String[N];
        sort(a,0,N-1,0);
    }

    private static void sort(String[] a, int lo,int hi, int d) {
        StdOut.println("lo："+lo+" hi："+hi);
        //以第d个字符为键将a[lo]..a[hi]排序
        if(hi<=lo+M){
            insertion(a,lo,hi,d);
            //修改后的插入排序
            return;
        }
        int count[]=new int[R+2];
        for (int i=lo;i<hi;i++){
            count[charAt(a[i],d)+2]++;
        }
        for (int r=0;r<R+1;r++){
            count[r+1]+=count[r];
        }
        for (int i=lo;i<=hi;i++){
            aux[count[charAt(a[i],d)+1]++]=a[i];
        }
        for (int i=lo;i<=hi;i++){
            a[i]=aux[i-lo];
        }
        for (int r=0;r<R;r++){
            int newLo=lo+count[r];
            int newHi=lo+count[r+1]-1;

            sort(a,newLo,newHi,d+1);
        }
    }
    // insertion sort a[lo..hi], starting at dth character
    private static void insertion(String[] a, int lo, int hi, int d) {
        for (int i = lo; i <= hi; i++)
            for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
                exch(a, j, j-1);
    }

    // exchange a[i] and a[j]
    private static void exch(String[] a, int i, int j) {
        String temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // is v less than w, starting at character d
    private static boolean less(String v, String w, int d) {
        // assert v.substring(0, d).equals(w.substring(0, d));
        for (int i = d; i < Math.min(v.length(), w.length()); i++) {
            if (v.charAt(i) < w.charAt(i)) return true;
            if (v.charAt(i) > w.charAt(i)) return false;
        }
        return v.length() < w.length();
    }


    public static void main(String[] args){
        String[] a={
                "she",
                "sells",
                "seashells",
                "by",
                "the",
                "sea",
                "shore",
                "the",
                "shells",
                "she",
                "sells",
                "are",
                "surely",
                "seashells",
        };

        MSD.sort(a);

        Printer.printArray(a);
    }

}
